#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define SIZE1 10000
#define SIZE2 20000
#define SIZE3 30000
#define SIZE4 40000

//////// Buble Sort ///////
// Best Case is ASC sorted List
// Worst Case is DESC Sorted List

void swap(int *a, int *b)
{  int temp;
   temp = *a;
   *a = *b;
   *b = temp;
}

void bubble_sort(int ar[], int size)
{  int i, j;
   for (i = 0; i < size; i++)
      for (j = i + 1; j < size; j++)
         if (ar[i] > ar[j])
            swap(&ar[i],&ar[j]);
}






//////// Insertion Sort /////////
// Best Case is ASC sorted List
// Worst Case is DESC Sorted List
void insertion_sort(int a[], int size)
{
	int i=0;
	int j;
	int tmp;
	for(i = 1; i < size; i++)
	{
		tmp= a[i];
		j = i -1;
		while((j >= 0) && (tmp< a[j]))
		{
			a[j+ 1] = a[j];
			j = j -1;
		}
		a[j+ 1] = tmp;
	}
}



/////////////Merge Sort/////////////
/*  ////////  From book /////////
void merge(int A[], int p, int q, int r){
	int n1 = q-p;
	int n2 = r-q-1;
	int L[n1] = {0};
	int R[n2] = {0};
	int i,j,k;
	for (i=0; i < n1 ;i++ ){
		L[i] = A[p+i-1];
	}
	for (j=0;j < n2 ;j++ ){
		R[j] = A[q+j];
	}
	L[n1+1] = 0;
	R[n2+1] = 0;
	i=0; j=0;
	for (k=p;j < r ;k++ ){
		if (L[i]<=R[j]){
			A[k] = L[i];
			i=i+1;
		}else{
			A[k] = R[j];
			j=j+1;
		}
	}
}
*/



void merge(int a[],int l, int m,int r,int size)
{
	int *c;
	int i,j,k;
	c = (int *)malloc(size * sizeof(int)); 
	i=l;
	j=m+1;
	k=l;

	while((i<=m) && (j<=r))
	{
		if(a[i]<a[j])
			c[k++]=a[i++];
		else
			c[k++]=a[j++];
	}
	while(i<=m)
		c[k++]=a[i++];

	while(j<=r)
		c[k++]=a[j++];
	
	for(i=l;i<=r;i++)
	{
		a[i]=c[i];
	}
	free(c);
	
}


void merge_sort(int a[],int l, int r)
{
	 int m = ( l+r )/2;
	if (r > l)
	{
		
    	merge_sort(a, l, m);  
		merge_sort(a, m+1, r);
		merge(a, l, m, r, l+r+1);
	}
}



///////// Print screen Array ///////////
void printArr(int ar[],int size){
	int i;
	for (i = 0;i<size;i++){
		printf("%d ",ar[i]);
	}
}

////////// Fill array list /////////
void fillArray(int ar[],int size,int type){

	/*
		1 => random
		2 => asc sorted
		3 => desc sorted
	*/
	
	int i;
	if (type == 1){
		srand(time(NULL));
		for (i = 0;i<size;i++){
			ar[i] = rand()%1000;
		}
	}else if (type == 2){
		for (i = 0;i<size;i++){
			ar[i] = i;
		}
	}else if (type == 3){
		for (i = 0;i<size;i++){
			ar[i] = size-i;
		}
	}
}


void sortStart(int arr[],int size,int type){
	/*
		10 => insertion[random]
		11 => insertion[ASC sorted]
		12 => insertion[DESC sorted]
		
		
		20 => bubble[random]
		21 => bubble[ASC sorted]
		22 => bubble[DESC sorted]

  
		30 => merge[random]
		31 => merge[ASC sorted]
		32 => merge[DESC sorted]

		*/

	clock_t start;
	clock_t end;



	if (type >= 10 && type <20){

		
		start = clock();
		insertion_sort(arr, size);
		end = clock();

		printf("Running time with %d array (%s) with insertion sort is : %f \n",size,
			((type==10)?("random list"):( (type==11)?("ASC Sorted"):("DESC Sorted") )),
			(end-start)/ (double)CLOCKS_PER_SEC);
	
	}else if (type >= 20 && type <30){

		
		start = clock();
		bubble_sort(arr, size);
		end = clock();

		printf("Running time with %d array (%s) with bubble sort is : %f \n",size,
			((type==20)?("random list"):( (type==21)?("ASC Sorted"):("DESC Sorted") )),
			(end-start)/ (double)CLOCKS_PER_SEC);
	
	}else if (type >= 30 && type <40){

		
		start = clock();
		//merge_sort(int ar[],int first,int last)
		merge_sort(arr, 0, size-1);
		end = clock();

		printf("Running time with %d array (%s) with merge sort is : %f \n",size,
			((type==30)?("random list"):( (type==31)?("ASC Sorted"):("DESC Sorted") )),
			(end-start)/ (double)CLOCKS_PER_SEC);
	
	}

	

	
}

int main(){

	int ar1[SIZE1] = {0};
	int ar2[SIZE2] = {0};
	int ar3[SIZE3] = {0};
	int ar4[SIZE4] = {0};
	
	
    // For insertion
		// SIZE1
		//random
		fillArray(ar1,SIZE1,1);
		sortStart(ar1,SIZE1,10);
		// asc sorted
		fillArray(ar1,SIZE1,2);
		sortStart(ar1,SIZE1,11);
		// desc Sorted
		fillArray(ar1,SIZE1,3);
		sortStart(ar1,SIZE1,12);

		// SIZE2
		//random
		fillArray(ar2,SIZE2,1);
		sortStart(ar2,SIZE2,10);
		// asc sorted
		fillArray(ar2,SIZE2,2);
		sortStart(ar2,SIZE2,11);
		// desc Sorted
		fillArray(ar2,SIZE2,3);
		sortStart(ar2,SIZE2,12);

		
		// SIZE3
		//random
		fillArray(ar3,SIZE3,1);
		sortStart(ar3,SIZE3,10);
		// asc sorted
		fillArray(ar3,SIZE3,2);
		sortStart(ar3,SIZE3,11);
		// desc Sorted
		fillArray(ar3,SIZE3,3);
		sortStart(ar3,SIZE3,12);

		// SIZE4
		//random
		fillArray(ar4,SIZE4,1);
		sortStart(ar4,SIZE4,10);
		// asc sorted
		fillArray(ar4,SIZE4,2);
		sortStart(ar4,SIZE4,11);
		// desc Sorted
		fillArray(ar4,SIZE4,3);
		sortStart(ar4,SIZE4,12);

	//For buble sort
		// SIZE1
		//random
		fillArray(ar1,SIZE1,1);
		sortStart(ar1,SIZE1,20);
		// asc sorted
		fillArray(ar1,SIZE1,2);
		sortStart(ar1,SIZE1,21);
		// desc Sorted
		fillArray(ar1,SIZE1,3);
		sortStart(ar1,SIZE1,22);

		// SIZE2
		//random
		fillArray(ar2,SIZE2,1);
		sortStart(ar2,SIZE2,20);
		// asc sorted
		fillArray(ar2,SIZE2,2);
		sortStart(ar2,SIZE2,21);
		// desc Sorted
		fillArray(ar2,SIZE2,3);
		sortStart(ar2,SIZE2,22);

		// SIZE3
		//random
		fillArray(ar3,SIZE3,1);
		sortStart(ar3,SIZE3,20);
		// asc sorted
		fillArray(ar3,SIZE3,2);
		sortStart(ar3,SIZE3,21);
		// desc Sorted
		fillArray(ar3,SIZE3,3);
		sortStart(ar3,SIZE3,22);

		// SIZE4
		//random
		fillArray(ar4,SIZE4,1);
		sortStart(ar4,SIZE4,20);
		// asc sorted
		fillArray(ar4,SIZE4,2);
		sortStart(ar4,SIZE4,21);
		// desc Sorted
		fillArray(ar4,SIZE4,3);
		sortStart(ar4,SIZE4,22);
		


	//For merge sort
		// SIZE1
		//random
		fillArray(ar1,SIZE1,1);
		sortStart(ar1,SIZE1,30);
		// asc sorted
		fillArray(ar1,SIZE1,2);
		sortStart(ar1,SIZE1,31);
		// desc Sorted
		fillArray(ar1,SIZE1,3);
		sortStart(ar1,SIZE1,32);

		// SIZE2
		//random
		fillArray(ar2,SIZE2,1);
		sortStart(ar2,SIZE2,30);
		// asc sorted
		fillArray(ar2,SIZE2,2);
		sortStart(ar2,SIZE2,31);
		// desc Sorted
		fillArray(ar2,SIZE2,3);
		sortStart(ar2,SIZE2,32);

		// SIZE3
		//random
		fillArray(ar3,SIZE3,1);
		sortStart(ar3,SIZE3,30);
		// asc sorted
		fillArray(ar3,SIZE3,2);
		sortStart(ar3,SIZE3,31);
		// desc Sorted
		fillArray(ar3,SIZE3,3);
		sortStart(ar3,SIZE3,32);

		// SIZE4
		//random
		fillArray(ar4,SIZE4,1);
		sortStart(ar4,SIZE4,30);
		// asc sorted
		fillArray(ar4,SIZE4,2);
		sortStart(ar4,SIZE4,31);
		// desc Sorted
		fillArray(ar4,SIZE4,3);
		sortStart(ar4,SIZE4,32);
	
    getch();
	return 0;
}
